package com.salim.leetcode.$51;

import java.util.*;

public class NQueens {

    class Dot{
        int i = 0;
        int j = 0;
        public Dot(int i,int j){
            this.i = i;
            this.j = j;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<length;i++){
                if(i==this.j){
                    sb.append("Q");
                }else{
                    sb.append(".");
                }
            }
            return sb.toString();
        }
    }
    public List<List<String>> result = new ArrayList<>();
    public int length = 0;
    public Map<String,Integer> leftDiagonalDots = new HashMap<>();
    public Map<String,Integer> rightDiagonalDots = new HashMap<>();
    public List<List<String>> solveNQueens(int n) {
        if(n==0){
            result.add(new ArrayList<>());
            return result;
        }
        length = n;
        List<Integer> avaliableJ = new ArrayList<>();
        for(int i=0;i<n;i++){
            avaliableJ.add(i);
            if(i==0){
                leftDiagonalDots.put("0.0",n-1);
                rightDiagonalDots.put("0."+(n-1),n-1);
            }else{
                leftDiagonalDots.put("0."+i,n-1-i);
                leftDiagonalDots.put(i+".0",n-1+i);
                rightDiagonalDots.put("0."+(n-1-i),n-1-i);
                rightDiagonalDots.put(i+"."+(n-1),n-1+i);
            }
        }
        loop(new ArrayList<>(),new boolean[length],new boolean[2*length-1],new boolean[2*length-1]);
        return result;
    }

    public void loop(List<Dot> dotList,boolean[] usedJ,boolean[] leftDiagonalUsed,boolean[] rightDiagonalUsed){
        for(int j=0;j<usedJ.length;j++){
            if(usedJ[j]){
                continue;
            }
            int leftLine = getLeftDiagonalLine(dotList.size(),j);
            int rightLine = getRightDiagonalLine(dotList.size(),j);
            if(leftDiagonalUsed[leftLine]){
                continue;
            }
            if(rightDiagonalUsed[rightLine]){
                continue;
            }

//            List<Dot> newDotList = new ArrayList<>(dotList);
//            newDotList.add(new Dot(length-avaliableJ.size(),currentJ));
            dotList.add(new Dot(dotList.size(),j));
            leftDiagonalUsed[leftLine] = true;
            rightDiagonalUsed[rightLine] = true;
            usedJ[j] = true;

            if(dotList.size()==length){
                result.add(toList(dotList));
            }else{
                loop(dotList,usedJ,leftDiagonalUsed,rightDiagonalUsed);
            }
            dotList.remove(dotList.size()-1);
            leftDiagonalUsed[leftLine] = false;
            rightDiagonalUsed[rightLine] = false;
            usedJ[j] = false;
        }
    }

    public List<String> toList(List<Dot> dotList){
        List<String> result = new ArrayList<>();
        for (int i=0;i<dotList.size();i++){
            result.add(dotList.get(i).toString());
        }
        return result;
    }

    /**
     * 判断属于左对角线的第几根
     * 左在上右在下的对角线
     * ↖
     *   ↘
     *   3 2 1 0
     * 3 * * * *
     * 4 * * * *
     * 5 * * * *
     * 6 * * * *
     * 总共有2n-1根线
     * @param i
     * @param j
     * @return
     */
    public int getLeftDiagonalLine(int i,int j){
        if(i>j){
            return leftDiagonalDots.get((i-j)+"."+0);
        }else{
            return leftDiagonalDots.get(0+"."+(j-i));
        }
    }

    /**
     * 判断属于右对角线的第几根
     * 右在上左在下的对角线
     *     ↗
     * ↙
     *   0 1 2 3
     *   * * * * 3
     *   * * * * 4
     *   * * * * 5
     *   * * * * 6
     * 总共有2n-1根线
     * @param i
     * @param j
     * @return
     */
    public int getRightDiagonalLine(int i,int j){
        if(j>length-1-i){
            return rightDiagonalDots.get((i-(length-1-j))+"."+(length-1));
        }else{
            return rightDiagonalDots.get(0+"."+(i+j));
        }
    }

    public static void main(String[] args) {
        NQueens fun = new NQueens();
        fun.solveNQueens(4);
    }
}
